Broadcast communication is simultaneous communication from a server (transmitting device) to a plurality of nodes (receiving devices) on a network. In a case of transmitting an identical content from a server to a plurality of nodes, use of the broadcast communication significantly improves communication efficiency in comparison with a case of repeating one-to-one communication between the server and each of the nodes. Thus, the broadcast communication is advantageous particularly in radio communication, not only for television broadcasting and radio broadcasting, but also for the Internet and a sensor network. In recent years, due to increasing cyber-attacks, the broadcast communication has been also demanded to take measures for information security, and it has become important to perform data authentication that verifies whether data received by each node is data transmitted from a server.
In general, a node may be often provided at a place directly accessible by an attacker. In addition, security measures on a node may be often insufficient because of performance degradation and cost increase involved in the security measures. Thus, a node has a higher possibility of leakage of confidential information than a server. The broadcast communication needs a data authentication scheme in consideration of such a situation.
Data authentication using cryptography is roughly classified into two types, which are digital signature using public-key cryptography and message authentication using common-key cryptography.
In the digital signature, a server holds a secret key for signature generation, and a node holds a public key for signature verification. Since it is difficult to estimate the secret key from the public key because of a nature of the public-key cryptography, an attacker attacking the node is unable to obtain the secret key necessary for signature generation. Therefore, it is difficult to falsify broadcast data. However, the digital signature using the public-key cryptography has a problem that a computation amount and a communication amount (signature length) are extremely large in comparison with the message authentication using the common-key cryptography. Thus, in a network constituted of small-sized nodes such as sensors, it is preferable to use the low-complexity message authentication.
FIG. 10 is a diagram illustrating how general message authentication works.
In the message authentication, a server and a node share a secret key in advance. The server generates a tag T from transmission data D and a counter value n through cipher processing, and transmits the tag T with the data D. The counter value n is used to prevent a replay attack and is incremented for each object to be authenticated such as a packet. The node holds a received counter value, and when the received counter value n′ is appropriately updated from a currently held counter value, the node determines that received data is not data transmitted in the replay attack. When this determination is passed, the node generates a tag from the received data D′ and the counter value n′ through cipher processing, similarly to the server. When the generated tag matches with a received tag T′, the node determines that the received data D′ is valid data (D′=D) from the server.
As message authentication processing using block cipher, a CMAC (Cipher-based MAC algorithm) based on a CBC-MAC (Cipher Block Chaining MAC algorithm) as disclosed in NPL 1 is often used. In addition, as message authentication processing using a cryptographic hash function, a HMAC (Keyed-Hash Message Authentication Code) as disclosed in NPL 2 is often used.
Message authentication in broadcast communication (hereinafter called broadcast authentication) can be realized by, for example, a server and all nodes sharing a secret key. At this time, leakage of the secret key from one node may cause broadcast data to be falsified very easily and affects all the nodes.
As one method of enhancing security of the broadcast authentication using the common-key cryptography, message authentication using a plurality of secret keys is known. A server holds a set L of secret keys, and a node u holds a subset L(u) of the set L. The server generates tags for data to be broadcast by using all secret keys of the set L and transmits the tags with the data. The node u generates tags from received data by using all secret keys of the subset L(u). When all the generated tags respectively match corresponding tags included in received tags, the node u determines that the received data is data transmitted from the server.
In addition, as another method of enhancing security of the broadcast authentication using the common-key cryptography, Timed Efficient loSs-toLerant Authentication (TESLA) is disclosed in NPL 3.
In the TESLA, a server generates a secret key for message authentication by using a one-way chain. The server calculates secret keys K[n−1], . . . , K[0] by using a random secret key K[n] and a one-way function f in accordance with Math. 1.K[i]=f(K[i+1]),i=N−1,N−2, . . . ,1,0  [Math. 1]
Herein, N is a length of a chain. The length of a chain is a parameter that determines the number of message authentications executable for one setting of a secret key K[0] from a server to a node. In an initial setting, the server generates and holds a chain of the secret keys and sets a secret key K[0] to a node. For the setting of the secret key K[0], one-to-one communication between the server and each node or normal digital signature is used. When the digital signature is used, a secret key K[0] received by the node is verified as being the secret key K[0] transmitted from the server.
In the TESLA, when broadcasting pieces of data D[1], . . . , D[n], a server generates tags for message authentications by using secret keys K[1], . . . , K[n], respectively, and transmits the tags. When data D[i] indicates entire pieces of transmission data within a time slot, the server generates a tag for each piece of the transmission data in the data D[i] by using a secret key K[i].
The server transmits the secret key K[i] after a lapse of a certain time from transmitting the data D[i]. A node holds a secret key K[i′] (i′<i). After receiving a secret key K[i], the node confirms that the secret key K[i] is the valid secret key K[i] transmitted from the server by verifying that a value of the secret key K[i] obtained by (i−i′)-time application of the one-way function f matches the held secret key K[i′]. The node authenticates the data D[i] after the verification of the secret key K[i]. In addition, the node is prepared for receiving a secret key K[i+1] by holding the secret key K[i].
In the TESLA, by delaying disclosure of a secret key with respect to transmitting of data and a tag for message authentication, a node is able to confirm that received data is data from a server knowing a valid secret key. In addition, the node does not hold a secret key K[i] at a point of time when the server transmits data D[i]. Thus, an attacker attacking the node is unable to acquire the secret key K[i] at the point of time, and it is difficult to generate a tag T[i] for data other than the data D[i]. In addition, in comparison with general one-to-one-communication message authentication, increase in a communication amount and a computation amount is relatively small. Thus, the TESLA is more efficient than the general one-to-one-communication message authentication.
Note that, as a related art, PTL 1 discloses a technique of using a one-way function in a digital signature scheme that uses public-key cryptography. In addition, PTL 2 discloses a technique of performing authentication of inter-device communication by using authentication information generated with a one-way function.